package com.wc._16届国特冲刺营._01暴力拆解.X质数;
import java.util.Scanner;

/**
 * @Author congge
 * @Date 2025/5/6 17:03
 * @description https://www.lanqiao.cn/courses/51805/learning/?id=4071536&compatibility=false
 */


public class Main {
    static int N = 1000010;
    static boolean[] st = new boolean[N];
    static int[] primes = new int[N / 10];
    static int idx = 0;

    static void ola(){
        st[0] = st[1] = true;
        for(int i = 2; i <= N - 1; i++){
            if(!st[i]) primes[++idx] = i;
            for(int j = 1; primes[j] <= (N - 1) / i; j++){
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }

    static int[] nums = new int[10];
    static int len = 0;
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        ola();
        int res = 0;
        // System.out.println(idx);
        for(int i = 1; i <= 1000000; i++){
            int x = i;
            if(!st[x]) {
                res++;
                // System.out.print(i + " ");
                continue;
            }
            len = String.valueOf(x).length();
            for(int j = len - 1; j >= 0; j--){
                nums[j] = x % 10;
                x /= 10;
            }
            // for(int j = 0; j < len; j++) System.out.print(nums[j]);
            // System.out.println();
            for(int j = 1; j < 1 << len; j++){
                int s = 0;
                for(int k = 0; k < len; k++){
                    if((j >> k & 1) == 1) s = s * 10 + nums[k];
                }
                // System.out.println(s);
                if(!st[s]) {
                    res++;
                    // System.out.print(i + " ");
                    break;
                }
            }
        }
        System.out.println(res);
    }
}
